// Copyright 2011 Jefferson Willian
// willmont7@gmail.com

#include <cstdio>

#define MAX(a, b) b>a?b:a

int main() {
  int max, cards;
  int peso[51][2];
  int din[51][1001];
  int games = 1;

  while (scanf("%d%d", &max, &cards) && max != 0 || cards != 0) {
    for (int i = 0;i < cards;i++)
      scanf("%d%d", &peso[i][0], &peso[i][1]);

    for (int i = 0;i <= max;i++)
      din[0][i] = 0;
    for (int i = 0;i < 51;i++)
      din[i][0] = 0;

    /* [MODELAGEM]Knapsack Problem - Programacao dinamica */
    for (int i = 0;i < cards;i++)
      for (int j = 1;j <= max;j++) {
        if (peso[i][0] > j)
          din[i+1][j] = din[i][j];
        else
          din[i+1][j] = MAX(din[i][j], din[i][j-peso[i][0]]+peso[i][1]);
      }

    printf("Teste %d\n%d\n\n", games++, din[cards][max]);
  }

  return 0;
}
